package niuke;
import java.util.*;
class Student{
    private String stuNo;
    private String name;
    private String sex;
    private int age;
    public static int count;
    public Student(String s1, String s, int i){
        count++;
    }
    public Student(String stuNo, int age) {
        this.stuNo = stuNo;
        this.name = name;
        this.sex = sex;
        this.age = age;
        count++;
    }
    public void info(){
        String st=this.toString();
        System.out.println(st);
    }
    @Override
    public String toString() {
        return "学号是"+this.stuNo+";姓名是"+this.name+";年龄是"+this.age+";性别是"+this.sex;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return Objects.equals(stuNo, student.stuNo);
    }
}
public class niuKeMain8 {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array==null){
            return 0;
        }
        int max=array[0];
        int max1=0;
        for (int i = 0; i < array.length; i++) {
            max1+=array[i];
            if (max<=max1){
                max=max1;
            }
            if (max1<0){
                max1=0;
            }

        }
        return max;
    }
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] arr=new int[m][n];
        for (int i = 0; i < m; i++) {
            arr[i][0]=1;
        }
        for (int i = 0; i < n; i++) {
            arr[0][i]=1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                arr[i][j]=arr[i][j-1]+arr[i-1][j];
            }
        }
        return arr[m-1][n-1];
    }
    public double maxProduct(double[] arr) {
        double res=arr[0];
        double min=arr[0];
        double max=arr[0];
        for (int i = 1; i < arr.length; i++) {
            double max1=max;
            max=Math.max(Math.max(arr[i], arr[i] * max), min * arr[i]);
            min=Math.min(Math.min(arr[i],arr[i]*min),max1*arr[i]);
            res=Math.max(max,res);
        }
        return res;
    }
    ArrayList<String> res=null;
    public ArrayList<String> getSolution(int n) {
        // write code here
        if (n==0){
            return null;
        }
        res=new ArrayList<>();
        func(n,"left","mid","right");
        return res;
    }
    private void func(int n, String from, String mid, String to) {
        if (n==1){
            res.add("move from "+from+" to "+to);
        }
        else{
            func(n-1,from,to,mid);
            func(1,from,mid,to);
            func(n-1,mid,from,to);
        }
    }
}
